﻿namespace LuckyFish.CalculatorLib;

public class ReversePolishCalculator
{
    public static double Calculator(string? input)
    {
        if (string.IsNullOrEmpty(input)) return 0;
        var operandList = AnalysisOperand(input);
        // 将链表数据转化成逆波兰表达式
        var reversePolishNotationList = Parse2ReversePolishNotation(operandList);
        // 计算逆波兰表达式
        return CountReversePolishNotation(reversePolishNotationList);
    }

    #region 中缀表达式拆分成数值和符号保存到链表上

    /// <summary> 算式分解存储在链表上 </summary>
    private static LinkedList<object> AnalysisOperand(string input)
    {
        var operand = new LinkedList<object>();
        if (string.IsNullOrEmpty(input))
            return operand;

        var startIdx = 0;
        var symbolIdx = 0;
        for (int i = 0, n = input.Length; i < n; ++i)
        {
            var curChar = input[i];
            if (curChar is >= '0' and <= '9' or ' ' or '.')
            {
                // 数字 空格 ., 此时表示读取到数值了
                // 将前面的运算符取出来
                ExtractOperation(input, ref symbolIdx, i, ref operand);
            }
            else
            {
                // 遇到非数字相关, 提取出前面的数字
                if (startIdx != i)
                {
                    // 添加数值
                    var valueStr = input.Substring(startIdx, i - startIdx);
                    var value = StringConvertDouble(valueStr);
                    operand.AddLast(value);
                }

                startIdx = i + 1;
            }
        }

        // 提取末尾的数据
        var fineChar = input[^1];
        if (fineChar is >= '0' and <= '9' or ' ' or '.')
        {
            // 数字 空格 ., 此时表示末尾数据是数字
            // 将前面的数值取出来
            var valueStr = input.Substring(startIdx, input.Length - startIdx);
            var value = StringConvertDouble(valueStr);
            operand.AddLast(value);
        }
        else
        {
            // 将前面的符号取出来
            ExtractOperation(input, ref symbolIdx, input.Length, ref operand);
        }

        //PrintLinkList(operand, "中缀表达式:");

        return operand;
    }

    /// <summary> 提取运算符 </summary>
    private static void ExtractOperation(string input, ref int symbolSubIdx, int endIdx, ref LinkedList<object> operand)
    {
        if (symbolSubIdx == endIdx)
        {
            // 指定位置无法提取运算符, 将运算符的位置移动到下一个位置
            symbolSubIdx = endIdx + 1;
            return;
        }

        for (var i = symbolSubIdx; i < endIdx; ++i)
        {
            // 几位数符号
            var symbolUnit = i - symbolSubIdx + 1;
            var symbolStr = input.Substring(symbolSubIdx, i - symbolSubIdx + 1);
            if (symbolUnit == 1)
            {
                if (symbolStr.Equals(" ") || symbolStr.Equals("+") || symbolStr.Equals("-") || symbolStr.Equals("*") ||
                    symbolStr.Equals("/") ||
                    symbolStr.Equals("!") || symbolStr.Equals("^") || symbolStr.Equals("%") || symbolStr.Equals("(") ||
                    symbolStr.Equals(")"))
                {
                    // 空格, 加, 减, 乘, 除, 阶乘, 幂, 求余, 括号
                    operand.AddLast(symbolStr);
                    symbolSubIdx = i + 1;
                }
                else if (symbolStr.Equals("h"))
                {
                    if (operand.Count == 0 && operand.Last!.Value is string) continue;
                    var preOperand = (string)operand.Last!.Value;
                    // 前面是sin, cos, tan, cot, 则可以组合成4位的运算符
                    if (!preOperand.Equals("sin") && !preOperand.Equals("cos") && !preOperand.Equals("tan")) continue;
                    operand.RemoveLast();
                    operand.AddLast(preOperand + symbolStr);
                    symbolSubIdx = i + 1;
                }
            }
            else if (symbolUnit == 2)
            {
            }
            else if (symbolUnit == 3)
            {
                if (!symbolStr.Equals("sin") && !symbolStr.Equals("cos") && !symbolStr.Equals("tan")) continue;
                // sin, cos, tan, cot
                operand.AddLast(symbolStr);
                symbolSubIdx = i + 1;
            }
        }

        if (symbolSubIdx < endIdx)
        {
            Console.WriteLine($"提取符号失败, 符号:{input.Substring(symbolSubIdx, endIdx - symbolSubIdx)}");
        }

        symbolSubIdx = endIdx + 1;
    }

    /// <summary> str转double </summary>
    private static double StringConvertDouble(string str)
    {
        if (!double.TryParse(str, out var value))
        {
            Console.WriteLine($"字符串转化成数值失败, 字符串:{str}");
        }

        return value;
    }

    #endregion 中缀表达式拆分成数值和符号保存到链表上

    #region 将公式转换成逆波兰表达式

    /// <summary> 算式转化成逆波兰表达式 </summary>
    private static LinkedList<object> Parse2ReversePolishNotation(LinkedList<object> operandList)
    {
        // 运算符列表
        LinkedList<object> operationList = [];
        // 中间结果列表
        LinkedList<object> expressionList = [];

        foreach (var item in operandList)
        {
            if (item is double d)
            {
                // 如果是操作数，则直接追加到中间结果列表
                expressionList.AddLast(d);
            }
            else
            {
                if ((string)item == "(")
                {
                    // 如果是 ( ，则直接放到运算符列表尾部，等待下一个最近的 右括号 与之配对。
                    operationList.AddLast(item);
                }
                else if ((string)item == ")")
                {
                    // 如果是 ），则说明有一对括号已经配对(在表达式输入无误的情况下)。
                    // 丢弃它，然后从运算符列表中去除最后一个元素e，将e依次追加到中间结果列表里。一直循环，直到取出的最后一个元素e 是 左括号 ( ，同样丢弃他。
                    do
                    {
                        if (operationList.Count == 0)
                        {
                            Console.WriteLine($"不存在 (");
                            break;
                        }

                        if ((string)operationList.Last!.Value == "(")
                        {
                            operationList.RemoveLast();
                            break;
                        }

                        expressionList.AddLast(operationList.Last.Value);
                        operationList.RemoveLast();
                    } while (true);
                }
                else
                {
                    // 如果是运算符（用op1表示）
                    do
                    {
                        if (operationList.Count == 0 || (string)operationList.Last!.Value == "(")
                        {
                            // 如果运算符列表最后一个元素（用op2表示） 不是运算符，则二者没有可比性，则直接将此运算符op1压栈。 例如栈顶是左括号 ( ，或者栈为空。
                            operationList.AddLast((string)item);
                            break;
                        }

                        // 如果运算符列表最后一个元素（用op2表示） 是运算符 ，则比较op1和 op2的优先级。如果op1 > op2 ，则直接将此运算符op1压栈。
                        var compareResult = CompareOperand((string)operationList.Last.Value, (string)item);
                        if (compareResult < 0)
                        {
                            operationList.AddLast((string)item);
                            break;
                        }

                        // 如果不满足op1 > op2，则将op2出栈，并追加到中间结果列表，再试图将op1压栈，如果如果依然不满足 op1>新的栈顶op2，继续将新的op2弹出追加到储存中间结果列表 ，直到op1可以压入栈中为止。
                        expressionList.AddLast(operationList.Last.Value);
                        operationList.RemoveLast();
                    } while (true);
                }
            }
        }

        // 如果运算符列表中还有元素，则依次取出追加到中间结果列表后，就得到了后缀表达式
        for (var iter = operationList.Last; iter != null; iter = iter.Previous)
            expressionList.AddLast(iter.Value);

        return expressionList;
    }

    /// <summary> 比较运算符的优先级 </summary>
    private static int CompareOperand(string operand1, string operand2)
    {
        if (operand1 == operand2) return 0;

        var wightDic = new Dictionary<string, int>()
        {
            { "+", 0 }, { "-", 0 },
            { "*", 1 }, { "/", 1 }, { "%", 1 },
            { "!", 2 }, { "^", 2 },
            { "sin", 3 }, { "cos", 3 }, { "tan", 3 }, { "sinh", 3 }, { "cosh", 3 }, { "tanh", 3 }
        };

        if (!wightDic.TryGetValue(operand1, out var wight1))
        {
            Console.WriteLine($"比较运算符时找不到运算符权重, operand:{operand1}");
        }

        if (!wightDic.TryGetValue(operand2, out var wight2))
        {
            Console.WriteLine($"比较运算符时找不到运算符权重, operand:{operand2}");
        }

        return wight1 - wight2;
    }

    #endregion

    #region 逆波兰表达式计算

    /// <summary> 计算逆波兰表达式 </summary>
    private static double CountReversePolishNotation(LinkedList<object> reversePolishNotation)
    {
        if (reversePolishNotation.Count == 0)
        {
            return 0;
        }

        var calculateStack = new Stack<double>();

        for (var iter = reversePolishNotation.First; iter != null; iter = iter.Next)
        {
            if (iter.Value is double value)
            {
                calculateStack.Push(value);
            }
            else if (iter.Value is string iterValue)
            {
                var countNum = CountOperationResult(ref calculateStack, iterValue);
                calculateStack.Push(countNum);
            }
        }

        return calculateStack.Pop();
    }

    /// <summary> 根据符号计算结果 </summary>
    private static double CountOperationResult(ref Stack<double> calculateStack, string symbol)
    {
        if (symbol == "+")
        {
            return calculateStack.Pop() + calculateStack.Pop();
        }

        if (symbol == "-")
        {
            var num2 = calculateStack.Pop();
            return calculateStack.Pop() - num2;
        }

        if (symbol == "*")
        {
            return calculateStack.Pop() * calculateStack.Pop();
        }

        if (symbol == "/")
        {
            var num2 = calculateStack.Pop();
            return calculateStack.Pop() / num2;
        }

        if (symbol == "!")
        {
            var num = calculateStack.Pop();
            if (num == 0) return 1;
            if (num < 0)
            {
                Console.WriteLine("不能对符号进行阶乘");
                return 0;
            }

            if (num - Math.Floor(num) > 1e-6 || num > 125)
            {
                Console.WriteLine("小数或太大的数不能进行阶乘");
                return 0;
            }

            var result = 1;
            for (var i = (int)Math.Floor(num); i > 0; --i)
            {
                result *= i;
            }

            return result;
        }

        if (symbol == "^")
        {
            var num2 = calculateStack.Pop();
            return Math.Pow(calculateStack.Pop(), num2);
        }

        if (symbol == "%")
        {
            var num2 = calculateStack.Pop();
            return calculateStack.Pop() % num2;
        }

        if (symbol == "sin")
        {
            return Math.Sin(calculateStack.Pop());
        }

        if (symbol == "cos")
        {
            return Math.Cos(calculateStack.Pop());
        }

        if (symbol == "tan")
        {
            return Math.Tan(calculateStack.Pop());
        }

        if (symbol == "sinh")
        {
            return Math.Sinh(calculateStack.Pop());
        }

        if (symbol == "cosh")
        {
            return Math.Cosh(calculateStack.Pop());
        }

        if (symbol == "tanh")
        {
            return Math.Tanh(calculateStack.Pop());
        }

        if (symbol == " ")
        {
            return calculateStack.Pop();
        }

        Console.WriteLine($"不存在运算符:{symbol}");

        return calculateStack.Pop();
    }

    #endregion
}